Burst Balloons

LeetCode 312 | Difficulty: Hard

Hard

Problem Description

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the i^th balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.

Example 1:

Input: nums = [3,1,5,8]
Output: 167
Explanation:
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

Example 2:

Input: nums = [1,5]
Output: 10

Constraints:

- `n == nums.length`

- `1 <= n <= 300`

- `0 <= nums[i] <= 100`

Topics: Array, Dynamic Programming

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

---

Solutions

Solution 1: C# (Best: 201 ms)

Metric	Value
Runtime	201 ms
Memory	38.3 MB
Date	2022-02-14

Solution

public class Solution {
    public int MaxCoins(int[] nums) {
        int n = nums.Length;
    int[] arr = new int[n+2];
    for (int i = 1; i < n+1; i++)
    {
        arr[i] = nums[i-1];
    }
    arr[0] = 1; arr[n+1] = 1;
    
    int[,] dp = new int[n+2, n+2];
    for (int window = 1; window <= n; window++)
    {
        for (int left = 1; left <= n-window+1; left++)
        {
            int right = left + window - 1;
            for (int i = left; i <= right; i++)
            {
                dp[left,right] = Math.Max(dp[left,right], (arr[left-1]*arr[i]*arr[right+1]) + dp[left,i-1] + dp[i+1,right]);
            }
        }       
    }
    return dp[1,n];
    }
}

---

Complexity Analysis

Approach	Time	Space
DP (2D)	$O(n × m)$	$O(n × m)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.